# 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。 
# 
#  在「杨辉三角」中，每个数是它左上方和右上方的数的和。 
# 
#  
# 
#  
# 
#  示例 1: 
# 
#  
# 输入: numRows = 5
# 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
#  
# 
#  示例 2: 
# 
#  
# 输入: numRows = 1
# 输出: [[1]]
#  
# 
#  
# 
#  提示: 
# 
#  
#  1 <= numRows <= 30 
#  
# 
#  Related Topics 数组 动态规划 👍 1204 👎 0
from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        arr = []
        for i in range(1,numRows+1):
            arr.append([1]*i)
        for i in range(numRows):
            for j in range(i+1):
                if j!=0 and j!= len(arr[i])-1:
                   arr[i][j] = arr[i-1][j-1] + arr[i-1][j]
        return arr

# leetcode submit region end(Prohibit modification and deletion)
print(Solution().generate(5))